package year2023.dp;

import java.sql.SQLOutput;

public class Code03_RobotWalk {

    public static int ways1(int N, int start, int aim, int K){
        if (N < 2 || start < 1 || start > N || aim < 1 || aim > N){
            return -1;
        }

        return process1(start, K, aim, N);
    }

    //机器人当前来到的位置是cur
    //机器人还有rest步需要去走
    //最终的目标是aim
    //有哪些位置  1~N
    //返回机器人从cur出发,走过rest步,最后停在aim的方法数是多少？
    public static int process1(int cur, int rest, int aim, int N){
        if (rest == 0){ //如果已经不需要走了，走完了
            return cur == aim ? 1 : 0;
        }
        // rest > 0,还有步数要走！
        if (cur == 1){
            return process1(2, rest - 1, aim, N);
        }
        if (cur == N){
            return process1(N - 1,rest - 1, aim, N);
        }
        //停在中间位置
        return process1(cur - 1, rest - 1, aim, N) + process1(cur + 1, rest - 1, aim, N);
    }

    //cur 范围: 1~N
    // rest 范围: 0~K
    //缓存表
    public static int ways2(int N, int start, int aim, int K){
        int[][] dp = new int[N + 1][K + 1];
        for (int i = 0; i <= N; i++) {
            for (int j = 0; j <= K; j++) {
                dp[i][j] = -1;
            }
        }
        //dp就是缓存表
        //dp[cur][rest] == -1 -> process2(cur, rest)之前没算过
        //dp[cur][rest] != -1 -> process2(cur, rest)之前算过！ 返回值,dp[cur][rest]

        return process2(start, K, aim, N, dp);
    }


    public static int process2(int cur, int rest, int aim, int N, int[][] dp){
        if (dp[cur][rest] != -1){
            return dp[cur][rest];
        }
        //之前没算过
        int ans = 0;


        if (rest == 0){
            ans = cur == aim ? 1 : 0;
        }else if (cur == 1){
            ans = process2(2, rest - 1, aim, N, dp);
        }else if (cur == N){
            ans = process2(N - 1,rest - 1, aim, N, dp);
        }else {
            ans = process2(cur - 1, rest - 1, aim, N, dp)
                    + process2(cur + 1, rest - 1, aim, N, dp);
        }

        dp[cur][rest] = ans;
        return ans;
    }

    public static int ways3(int N, int start, int aim, int K){
        int[][] dp = new int[N + 1][K + 1];
        dp[aim][0] = 1; //dp[...][0] = 0;

        for (int rest = 1; rest <= K; rest++){//列

            //cur -> (1,N)
            dp[1][rest] = dp[2][rest - 1];
            for (int cur = 2; cur < N; cur++){
                dp[cur][rest] = dp[cur - 1][rest - 1] + dp[cur + 1][rest - 1];
            }
            dp[N][rest] = dp[N - 1][rest - 1];
        }

        return dp[start][K];
    }




    public static void main(String[] args) {
        System.out.println(ways1(4,2,4,4));
        System.out.println(ways2(4,2,4,4));
        System.out.println(ways3(4,2,4,4));
    }

}
